package 二分查找.easy;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 *
 */
@SuppressWarnings("all")
public class 寻找比目标字母大的最小字母 {
    public static void main(String[] args) {
        char[] letters = {'c', 'f', 'j'};
        char target = 'c';
        System.out.println(nextGreatestLetter(letters, target));
    }

    /**
     * 典型的二分 （按照二分法的模板写即可）
     * @param letters
     * @param target
     * @return
     */
    public static char nextGreatestLetter(char[] letters, char target) {
        // 下面考虑结果一定出现在letters中间的
        int i = 0;
        int j = letters.length - 1;
        char ans = letters[0];
        while(i <= j) {
            int mid = i + (j - i) >> 2;
            if(letters[mid] > target) { // 索引异常???
                ans = letters[mid];
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return ans;
    }
}
